<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>README</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h1 id="data-structures">Data Structures</h1>
    <p>Topics:</p>
    <ul>
      <li>Queues</li>
      <li>Doubly Linked Lists</li>
      <li>Binary Search Trees</li>
      <li>Heaps</li>
    </ul>
    <p>Stretch Goals:</p>
    <ul>
      <li>Generic Heaps</li>
      <li>AVL Trees</li>
      <li>LRU Caches</li>
    </ul>
    <h2 id="tasks">Tasks</h2>
    <ol type="1">
      <li>
        <p>
          Implement each data structure, starting with the queue. Make sure
          you’re in the approriate directory, then run
          <code>python3 test_[NAME OF DATA STRUCTURE].py</code> to run the tests
          for that data structure and check your progress. Get all the tests
          passing for each data structure.
        </p>
      </li>
      <li>
        <p>
          Open up the <code>Data_Structures_Questions.md</code> file, which asks
          you to evaluate the runtime complexity of each of the methods you
          implemented for each data structure. Add your answers to each of the
          questions in the file.
        </p>
      </li>
    </ol>
    <blockquote>
      <p>
        NOTE: The quickest and easiest way to reliably import a file in Python
        is to just copy and paste the file you want to import into the same
        directory as the file that wants to import. This obviously isn’t
        considered best practice, but it is the most reliable way to do it
        across all platforms.
      </p>
    </blockquote>
    <h3 id="queues">Queues</h3>
    <ul>
      <li>
        Should have the methods: <code>enqueue</code>, <code>dequeue</code>, and
        <code>len</code>.
        <ul>
          <li>
            <code>enqueue</code> should add an item to the back of the queue.
          </li>
          <li>
            <code>dequeue</code> should remove and return an item from the front
            of the queue.
          </li>
          <li><code>len</code> returns the number of items in the queue.</li>
        </ul>
      </li>
    </ul>
    <figure>
      <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/52/Data_Queue.svg/600px-Data_Queue.svg.png"
        alt="Image of Queue"
      />
      <figcaption>Image of Queue</figcaption>
    </figure>
    <h3 id="doubly-linked-lists">Doubly Linked Lists</h3>
    <ul>
      <li>
        The <code>ListNode</code> class, which represents a single node in the
        doubly-linked list, has already been implemented for you. Inspect this
        code and try to understand what it is doing to the best of your ability.
      </li>
      <li>
        The <code>DoublyLinkedList</code> class itself should have the methods:
        <code>add_to_head</code>, <code>add_to_tail</code>,
        <code>remove_from_head</code>, <code>remove_from_tail</code>,
        <code>move_to_front</code>, <code>move_to_end</code>,
        <code>delete</code>, and <code>get_max</code>.
        <ul>
          <li>
            <code>add_to_head</code> replaces the head of the list with a new
            value that is passed in.
          </li>
          <li>
            <code>add_to_tail</code> replaces the tail of the list with a new
            value that is passed in.
          </li>
          <li>
            <code>remove_from_head</code> removes the head node and returns the
            value stored in it.
          </li>
          <li>
            <code>remove_from_tail</code> removes the tail node and returns the
            value stored in it.
          </li>
          <li>
            <code>move_to_front</code> takes a reference to a node in the list
            and moves it to the front of the list, shifting all other list nodes
            down.
          </li>
          <li>
            <code>move_to_end</code> takes a reference to a node in the list and
            moves it to the end of the list, shifting all other list nodes up.
          </li>
          <li>
            <code>delete</code> takes a reference to a node in the list and
            removes it from the list. The deleted node’s
            <code>previous</code> and <code>next</code> pointers should point to
            each afterwards.
          </li>
          <li><code>get_max</code> returns the maximum value in the list.</li>
        </ul>
      </li>
      <li>
        The <code>head</code> property is a reference to the first node and the
        <code>tail</code> property is a reference to the last node.
      </li>
    </ul>
    <figure>
      <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/Doubly-linked-list.svg/610px-Doubly-linked-list.svg.png"
        alt="Image of Doubly Linked List"
      />
      <figcaption>Image of Doubly Linked List</figcaption>
    </figure>
    <h3 id="binary-search-trees">Binary Search Trees</h3>
    <ul>
      <li>
        Should have the methods <code>insert</code>, <code>contains</code>,
        <code>get_max</code>.
        <ul>
          <li>
            <code>insert</code> adds the input value to the binary search tree,
            adhering to the rules of the ordering of elements in a binary search
            tree.
          </li>
          <li>
            <code>contains</code> searches the binary search tree for the input
            value, returning a boolean indicating whether the value exists in
            the tree or not.
          </li>
          <li>
            <code>get_max</code> returns the maximum value in the binary search
            tree.
          </li>
          <li>
            <code>for_each</code> performs a traversal of <em>every</em> node in
            the tree, executing the passed-in callback function on each tree
            node value. There is a myriad of ways to perform tree traversal; in
            this case any of them should work.
          </li>
        </ul>
      </li>
    </ul>
    <figure>
      <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/300px-Binary_search_tree.svg.png"
        alt="Image of Binary Search Tree"
      />
      <figcaption>Image of Binary Search Tree</figcaption>
    </figure>
    <h3 id="heaps">Heaps</h3>
    <ul>
      <li>
        Should have the methods <code>insert</code>, <code>delete</code>,
        <code>get_max</code>, <code>_bubble_up</code>, and
        <code>_sift_down</code>.
        <ul>
          <li>
            <code>insert</code> adds the input value into the heap; this method
            should ensure that the inserted value is in the correct spot in the
            heap
          </li>
          <li>
            <code>delete</code> removes and returns the ‘topmost’ value from the
            heap; this method needs to ensure that the heap property is
            maintained after the topmost element has been removed.
          </li>
          <li>
            <code>get_max</code> returns the maximum value in the heap
            <em>in constant time</em>.
          </li>
          <li>
            <code>get_size</code> returns the number of elements stored in the
            heap.
          </li>
          <li>
            <code>_bubble_up</code> moves the element at the specified index
            “up” the heap by swapping it with its parent if the parent’s value
            is less than the value at the specified index.
          </li>
          <li>
            <code>_sift_down</code> grabs the indices of this element’s children
            and determines which child has a larger value. If the larger child’s
            value is larger than the parent’s value, the child element is
            swapped with the parent.
          </li>
        </ul>
      </li>
    </ul>
    <figure>
      <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Max-Heap.svg/501px-Max-Heap.svg.png"
        alt="Image of a Heap in Tree form"
      />
      <figcaption>Image of a Heap in Tree form</figcaption>
    </figure>
    <figure>
      <img
        src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Heap-as-array.svg/603px-Heap-as-array.svg.png"
        alt="Image of a Heap in Array form"
      />
      <figcaption>Image of a Heap in Array form</figcaption>
    </figure>
    <h2 id="stretch-goals">Stretch Goals</h2>
    <h3 id="generic-heaps">Generic Heaps</h3>
    <p>
      A max heap is pretty useful, but what’s even more useful is to have our
      heap be generic such that the user can define their own priority function
      and pass it to the heap to use.
    </p>
    <p>
      Augment your heap implementation so that it exhibits this behavior. If no
      comparator function is passed in to the heap constructor, it should
      default to being a max heap. Also change the name of the
      <code>get_max</code> function to <code>get_priority</code>.
    </p>
    <p>
      You can test your implementation against the tests in
      <code>test_generic_heap.py</code>. The test expects your augmented heap
      implementation lives in a file called <code>generic_heap.py</code>. Feel
      free to change the import statement to work with your file structure or
      copy/paste your implementation into a file with the expected name.
    </p>
    <h3 id="avl-tree">AVL Tree</h3>
    <p>
      An AVL tree (Georgy Adelson-Velsky and Landis’ tree, named after the
      inventors) is a self-balancing binary search tree. In an AVL tree, the
      heights of the two child subtrees of any node differ by at most one; if at
      any time they differ by more than one, rebalancing is done to restore this
      property.
    </p>
    <p>We define balance factor for each node as :</p>
    <pre><code>balanceFactor = height(left subtree) - height(right subtree)</code></pre>
    <p>
      The balance factor of any node of an AVL tree is in the integer range
      [-1,+1]. If after any modification in the tree, the balance factor becomes
      less than −1 or greater than +1, the subtree rooted at this node is
      unbalanced, and a rotation is needed.
    </p>
    <figure>
      <img
        src="https://s3.amazonaws.com/hr-challenge-images/0/1436854305-b167cc766c-AVL_Tree_Rebalancing.svg.png"
        alt="AVL tree rebalancing"
      />
      <figcaption>AVL tree rebalancing</figcaption>
    </figure>
    <p>
      Implement an AVL Tree class that exhibits the aforementioned behavior. The
      tree’s <code>insert</code> method should perform the same logic as what
      was implemented for the binary search tree, with the caveat that upon
      inserting a new element into the tree, it will then check to see if the
      tree needs to be rebalanced.
    </p>
    <p>
      How does the time complexity of the AVL Tree’s insertion method differ
      from the binary search tree’s?
    </p>
    <h3 id="lru-cache">LRU Cache</h3>
    <p>
      An LRU (Least Recently Used) cache is an in-memory storage structure that
      adheres to the
      <a
        href="https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)"
        >Least Recently Used</a
      >
      caching strategy.
    </p>
    <p>
      In essence, you can think of an LRU cache as a data structure that keeps
      track of the order in which elements (which take the form of key-value
      pairs) it holds are added and updated. The cache also has a max number of
      entries it can hold. This is important because once the cache is holding
      the max number of entries, if a new entry is to be inserted, another
      pre-existing entry needs to be evicted from the cache. Because the cache
      is using a least-recently used strategy, the oldest entry (the one that
      was added/updated the longest time ago) is removed to make space for the
      new entry.
    </p>
    <p>
      So what operations will we need on our cache? We’ll certainly need some
      sort of <code>set</code> operation to add key-value pairs to the cache.
      Newly-set pairs will get moved up the priority order such that every other
      pair in the cache is now one spot lower in the priority order that the
      cache maintains. The lowest-priority pair will get removed from the cache
      if the cache is already at its maximal capacity. Additionally, in the case
      that the key already exists in the cache, we simply want to overwrite the
      old value associated with the key with the newly-specified value.
    </p>
    <p>
      We’ll also need a <code>get</code> operation that fetches a value given a
      key. When a key-value pair is fetched from the cache, we’ll go through the
      same priority-increase dance that also happens when a new pair is added to
      the cache.
    </p>
    <p>
      Note that the only way for entries to be removed from the cache is when
      one needs to be evicted to make room for a new one. Thus, there is no
      explicit <code>remove</code> method.
    </p>
    <p>
      Given the above spec, try to get a working implementation that passes the
      tests. What data structure(s) might be good candidates with which to build
      our cache on top of? Hint: Since our cache is going to be storing
      key-value pairs, we might want to use a structure that is adept at
      handling those.
    </p>
    <hr />
    <p>
      Once you’ve gotten the tests passing, it’s time to analyze the runtime
      complexity of your <code>get</code> and <code>set</code> operations.
      There’s a way to get both operations down to sub-linear time. In fact, we
      can get them each down to constant time by picking the right data
      structures to use.
    </p>
    <p>
      Here are you some things to think about with regards to optimizing your
      implementation: If you opted to use a dictionary to work with key-value
      pairs, we know that dictionaries give us constant access time, which is
      great. It’s cheap and efficient to fetch pairs. A problem arises though
      from the fact that dictionaries don’t have any way of remembering the
      order in which key-value pairs are added. But we definitely need something
      to remember the order in which pairs are added. Can you think of some ways
      to get around this constaint?
    </p>
  </body>
</html>
